// AllPath.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <list>
#include <string>
#include <vector>
using namespace std;

int size;
vector<list<string*>> v;

/*
	printAll about v
*/
void printAll()
{
	vector<list<string*>>::iterator iv;
	list<string*>::iterator il;
	for(iv=v.begin();iv!=v.end();iv++)
	{
		string s;
		il=(*iv).begin();
		s+=*(*il);
		il++;
		while(il!=(*iv).end())
		{
			s+="->";
			s+=*(*il);
			il++;
		}
		printf("%s\n",s.c_str());
	}
}

/*
	iterator of each List
*/
bool iteratorList(list<string*> l,string** first,string** second,string* exit)
{
	int i;
	for(i=0;i<size;i++)
		if(*(l.back())==*first[i])
		{
			//check the loop
			list<string*>::iterator il;
			list<string*>::iterator iltemp;
			list<string*>::iterator ile;
			list<list<string*>::iterator> ll;
			list<list<string*>::iterator>::iterator ill;
			bool check=true;
			for(il=l.begin();il!=l.end();il++)
				if(*(*il)==*second[i])
					ll.push_back(il);
			if(ll.size()>1)
				for(ill=ll.begin();ill!=ll.end();ill++)
				{
					ile=l.end();
					iltemp=(*ill);
					for(ile--;*(*ile)!=*second[i];ile--)
					{
						iltemp--;
						if(*(*iltemp)!=*(*ile)||ile==l.begin())
						{
							check=false;
							break;
						}
					}
					if(check)
						return true;
					check=true;
				}

			//go on push_back
			list<string*> l2;
			list<string*>::iterator ilcopy;
			for(ilcopy=l.begin();ilcopy!=l.end();ilcopy++)
				l2.push_back(*ilcopy);
			l2.push_back(second[i]);
			v.push_back(l2);
		}
	if(*(l.back())==*exit)
		return false;
	else
		return true;
}

/*
	iterator of each Vector
*/
void iteratorVector(string** first,string** second,string* exit)
{
	vector<list<string*>>::iterator iv=v.begin();
	int i=1;
	while(iv!=v.end())
		if(iteratorList(*iv,first,second,exit))
		{
			iv=v.begin();
			iv+=i-1;

			//erase the list we do not use
			v.erase(iv);
			iv=v.begin();
			iv+=i-1;
		}
		else
		{
			iv=v.begin();
			iv+=i;
			i++;
		}

	//print the result
	printAll();
}

/*
	MainFuction
*/
void MainFuction(list<pair<string,string>> l)
{
	//l can not be empty
	if(l.empty())
		exit(1);

	//put all pair.first into string** first
	//put all pair.second into string** second
	size=(int)l.size();
	list<pair<string,string>>::iterator il;
	string** first=(string**)malloc(size*4);
	string** second=(string**)malloc(size*4);
	int temp=0;
	for(il=l.begin();il!=l.end();il++)
	{
		first[temp]=&((*il).first);
		second[temp]=&((*il).second);
		temp++;
	}
	int temp2;

	//found entry
	string *entry,*exit;
	for(temp=0;temp<size;temp++)
	{
		for(temp2=0;temp2<size;temp2++)
			if(*first[temp]==*second[temp2])
			{
				temp2--;
				break;
			}
		if(temp2==size)
		{
			entry=first[temp];
			break;
		}
	}

	//found exit
	for(temp=0;temp<size;temp++)
	{
		for(temp2=0;temp2<size;temp2++)
			if(*second[temp]==*first[temp2])
			{
				temp2--;
				break;
			}
		if(temp2==size)
		{
			exit=second[temp];
			break;
		}
	}
	list<string*> l1;
	l1.push_back(entry);
	v.push_back(l1);

	//START
	iteratorVector(first,second,exit);
}

/*
	example1
*/
void example1(list<pair<string,string>>* l)
{	
	l->push_back(pair<string,string>("b","c"));
	l->push_back(pair<string,string>("acc","b"));
	l->push_back(pair<string,string>("acc","d"));
	l->push_back(pair<string,string>("d","b"));
	l->push_back(pair<string,string>("c","e"));
	l->push_back(pair<string,string>("b","e"));
}

/*
	example2
*/
void example2(list<pair<string,string>>* l)
{
	l->push_back(pair<string,string>("h","b"));
	l->push_back(pair<string,string>("c","b"));
	l->push_back(pair<string,string>("c","d"));
	l->push_back(pair<string,string>("d","c"));
	l->push_back(pair<string,string>("b","e"));
	l->push_back(pair<string,string>("b","f"));
	l->push_back(pair<string,string>("a","b"));
	l->push_back(pair<string,string>("a","c"));
	l->push_back(pair<string,string>("f","g"));
	l->push_back(pair<string,string>("f","h"));
	l->push_back(pair<string,string>("g","h"));
}

/*
	main
*/
int _tmain(int argc, _TCHAR* argv[])
{
	//example1
	list<pair<string,string>> l;
	printf("example1\n");
	example1(&l);
	MainFuction(l);
	l.clear();
	v.clear();
	printf("\n");

	//example2
	printf("example2\n");
	example2(&l);
	MainFuction(l);
	printf("\n");

	//finish
	printf("end");
	getchar();
	return 0;
}

